package leetcode.editor.cn.util.graph;

import java.util.*;

public class GraphUtil {
    private static final GraphUtil instance = new GraphUtil();

    private GraphUtil() {
    }

    public static GraphUtil getInstance() {
        return instance;
    }

    public Node generateFromArray(String str) {
        String[] strs = str.replaceAll("\\s", "").split("\\],\\[");
        List<List<Integer>> lists = new ArrayList<>();
        for (int i = 0; i < strs.length; i++) {
            String[] cur = strs[i].split(",");
            List<Integer> inner = new ArrayList<>();
            int start = 0;
            int end = cur.length;
            if (i == 0) {
                start = 1;
                inner.add(Integer.parseInt(cur[0].substring(cur[0].length() - 1)));
            }
            if (i == strs.length - 1) end = cur.length - 1;
            for (int j = start; j < end; j++) {
                inner.add(Integer.parseInt(cur[j]));
            }
            if (i == strs.length - 1) {
                inner.add(Integer.parseInt(cur[0].substring(0, 1)));
            }
            lists.add(inner);
        }
        return generateFromArray(lists);
    }

    public Node generateFromArray(List<List<Integer>> lists) {
        if (lists == null || lists.size() == 1) return null;
        Map<Integer, Node> map = new HashMap<>();

        for (int i = 0; i < lists.size(); i++) {
            int curV = i + 1;
            map.putIfAbsent(curV, new Node(curV));

            List<Node> inner = new ArrayList<>();
            List<Integer> valList = lists.get(i);
            for (Integer v : valList) {
                map.putIfAbsent(v, new Node(v));
                map.get(curV).neighbors.add(map.get(v));
            }
        }

        return map.get(lists.get(0).get(0));
    }

    public String toString(Node node) {
        if (node == null) return null;
        StringBuilder sb = new StringBuilder();
        Set<Node> set = new HashSet<>();

        Deque<Node> deque = new ArrayDeque<>();
        deque.add(node);
        while (!deque.isEmpty()) {
            Node poll = deque.poll();
            sb.append(poll.val + " : ");
            set.add(poll);
            for (Node n : poll.neighbors) {
                if (!set.contains(n) && !deque.contains(n)) {
                    deque.add(n);
                }
                sb.append(n.val + ", ");
            }
            sb.deleteCharAt(sb.length() - 2);
            sb.append("\n");
        }

        return sb.toString();
    }

    public static void main(String[] args) {
        GraphUtil util = GraphUtil.getInstance();
        Node node = util.generateFromArray("[2,4],[1,3],[2,4],[1,3]");
        System.out.println(util.toString(node));
        node = util.generateFromArray("[2,4,5],[1,3],[2,4],[1,3],[1,3]");
        System.out.println(util.toString(node));
    }
}
